package com.leetcode.sorts.arrays.slide_window;

/**
 * @Author: WuPeng
 * @Date: 2021/5/21 2:50 下午
 *
 * 209：长度最小的子数组
 *      给定一个含有n个正整数的数组和一个正整数 target 。
 *      找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，
 *      并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *
 * 示例 1：
 *      输入：target = 7, nums = [2,3,1,2,4,3]
 *      输出：2
 *      解释：子数组[4,3]是该条件下的长度最小的子数组。
 *
 * 示例 2：
 *      输入：target = 4, nums = [1,4,4]
 *      输出：1
 *
 * 示例 3：
 *      输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 *      输出：0
 *
 */
public class MinLengthArray_209 {

    /**
     * 暴力破解
     */
    public static int solution_01(int[] nums, int target){
        int min_len = nums.length+1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target){
                return 1;
            }
            int tmp_target = nums[i];
            int tmp_length = 1;
            for (int j = i+1; j < nums.length; j++) {
                tmp_target += nums[j];
                tmp_length++;
                if (tmp_target >= target){
                    min_len = min_len > tmp_length ? tmp_length : min_len;
                }
            }
        }
        return (min_len == nums.length+1) ? 0 : min_len;
    }

    /**
     * 滑动窗口--确定窗口的滑动
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *      并不是 for 里放一个while就以为是 O(n^2)， 主要是看每一个元素被操作的次数，
     *      每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以
     *      时间复杂度是2 * n 也就是 O(n)。
     */
    public static int solution_02(int[] nums, int target){
        int min_len = nums.length+1;
        int slow = 0, sum = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            sum += nums[fast];
            while (sum >= target){
                min_len = min_len > (fast - slow + 1) ? (fast - slow + 1) : min_len;
                sum -= nums[slow++];
            }
        }
        return min_len == nums.length+1 ? 0 : min_len;
    }

    public static void main(String[] args) {
        int[] nums = {2,3,1,2,4,3};
        int target = 7;
        System.out.println(solution_01(nums, target));
        System.out.println(solution_02(nums, target));
    }

}
